1. Field of the Invention
The present invention generally relates to carry generation, and more particularly to carry generation in address calculation in a computer system.
2. Description of the Related Art
In a typical computer system, most addressing modes require an addition of two numbers to calculate a storage address. In one addressing mode, the two numbers can be in a base register and an index register. In another addressing mode, one of the two numbers can be in a base register, and the other number can be in the instruction being executed.
These addressing modes are used in accessing data cache in which storage blocks in an array of storage blocks are arranged in rows and columns. In order to speed up a data cache access, some N least significant bits of the two numbers are added in three addition portions. In the first addition portion, some most significant bits of the N bits of the first number are added to the corresponding bits of the second number. The result is used to select a row of storage blocks. The first addition portion is well known in prior art as Row Access Select (RAS). In the second addition portion, some next most significant bits of the N bits of the first number are added to the corresponding bits of the second number. The result is used to select a column of the storage blocks. The second addition portion is well known in prior art as Column Access Select (CAS). The combined effect of the first and second addition portions is a selection of a storage block in the array of storage blocks. In the third addition portion, the remaining bits of the N bits of the first number are added to the corresponding bits of the second number. The result is used to select a line of the selected storage block. The third addition portion is well known in prior art as Line Access Select (LAS).
A performance limitation arises with the foregoing addressing mode because the first and second addition portions of the addition of the two numbers do not take into account the carry from the third addition portion. Therefore, two paths corresponding to the carry being “0” and “1” must be taken by the first and second addition portions. As a result, two storage blocks are selected instead of one. When the carry is available after the third addition portion, it is determined which path is correct and which of the two storage blocks is correct. The result from the third addition portion is then used to select one line from the correct storage block. Therefore, there is a need to perform the third addition portion fast so that the carry is available as soon as possible.
Typically, in order to add two N-bit numbers, one half-adder and N−1 full-adders are used. These N adders combine to form a ripple-carry adder because the carry ripples through the N stages of the adder starting at the least significant bit to the most significant bit. The time needed for this carry propagation is in proportion to the number of bits N. The sum output of the ripple-carry adder is correct only after the carry appears at the most significant bit. The larger the number of bits N is, the slower the ripple-carry adder will be.
One technique to speed up the addition of two N-bit numbers is called carry look-ahead, and the adder using the technique is called a carry look-ahead adder. The carry look-ahead adder is faster than the ripple carry adder because the time needed to calculate the carry is independent of the number of bits N and is equal to the delay of several intermediate stages. The delay along these intermediate stages is also independent of the number of bits N. However, the implementation of these stages in prior art requires an implementation of an N×N And-Or-Inverter (AOI) function. If N is large, the implementation of the N×N AOI function becomes complex resulting in delay in the generation of the carry. Therefore, there is a need for an apparatus and method for generating the carry as fast as possible so that the correct path (with carry or without carry) can be determined as fast as possible.
Moreover, if result forwarding or bypass is implemented in the system, another logic level is required to implement the selection of different sources for the operand inputs of a carry generation circuit. Result forwarding or bypass is a technique of applying the result from a functional unit in a previous cycle to an address generator without first saving the result to a register file. Therefore, there is a need for an apparatus and method for reducing the number of logic levels in implementing the selection of different sources for the operand inputs of the carry generation circuit and for generating the carry.